The disclosed embodiments of the present invention relate to forwarding packets, and more particularly, to a packet processing apparatus and method using the flow subgroup based path selection for dynamic load balancing.
Routing is the process of selecting the best path from a source node to a destination node in a network environment. For example, the current Internet infrastructure consists of interconnected networks. A router, also known as a gateway, is a device that connects different networks together. The router's main tasks may include discovering paths to various destinations and forwarding packets inside the network or between different networks. When a router receives a packet at one of its incoming (ingress) ports, the header of the received packet is checked. When the destination address of the packet is known, the forwarding table lookup is performed to obtain the information to which outgoing (egress) port the packet should be sent.
The router may employ one routing protocol for packet forwarding. For example, ECMP (Equal Cost Multi-Path) is a technique for routing packets along multiple paths of equal cost. When forwarding a packet, the router must decide which next-hop (path) to use. One typical method for determining which next-hop (path) to use when routing with ECMP may employ the hash-based path selection. For example, the router first determines a hash value by performing a hash function upon the packet header fields that identify a flow. Multiple next-hops have been assigned unique hash values. Hence, the router uses the hash value derived from the packet to be forwarded to decide which next-hop (path) to use.
The hash-based path selection distributes flows to ECMP paths statistically. As a result, the hash-based path selection cannot guarantee a uniform bandwidth distribution over the ECMP paths. For example, one equal-cost egress path may be selected to deliver more flows, while another equal-cost egress path may be selected to deliver fewer flows. Further, the packet traffic in each flow may not be equal. Thus, there is a need for an innovative packet forwarding scheme which can applying dynamic load balancing to packet traffic over multiple egress paths to thereby achieve a more uniform bandwidth distribution.